Em matemática, o algoritmo de Euclides é um método simples e eficiente de encontrar o máximo divisor comum entre dois números inteiros diferentes de zero. É um dos algoritmos mais antigos, conhecido desde que surgiu nos Livros VII e X da obra Elementos de Euclides por volta de 300 a.C.. O algoritmo não exige qualquer fatoração.

O MDC de dois números inteiros é o maior número inteiro que divide ambos sem deixar resto. O algoritmo de Euclides é baseado no princípio de que o MDC não muda se o menor número for subtraído ao maior. Por exemplo, 21 é o MDC de 252 e 105 (252 = 21 × 12; 105 = 21 × 5); já que 252 − 105 = 147, o MDC de 147 e 105 é também 21. Como o maior dos dois números é reduzido, a repetição deste processo irá gerar sucessivamente números menores, até convergir em zero. Nesse momento, o MDC é o outro número inteiro, maior que zero. Ao reverter os passos do algoritmo de Euclides, o MDC pode ser expresso como soma dos dois números originais, cada um multiplicado por um número inteiro positivo ou negativo, por exemplo: 21 = 5 × 105 + (−2) × 252. Esta importante propriedade é denominada identidade de Bézout.

A mais antiga descrição que se conhece do método usado no algoritmo de Euclides é da sua obra Elementos (c. 300 a.C.), o que o torna um dos algoritmos numéricos mais antigos ainda em uso corrente. O algoritmo original foi descrito apenas para números naturais e comprimentos geométricos, mas foi generalizado no século XIX para outras classes de números como os inteiros gaussianos e polinómios de uma variável. Isto conduziu a noções da moderna álgebra abstrata tais como os domínios euclidianos. O algoritmo de Euclides foi ainda generalizado mais a outras estruturas matemáticas, como os nós e polinómios multivariados.

O algoritmo tem muitas aplicações teóricas e práticas. Ele pode ser usado para gerar quase todas as importantes aplicações tradicionais usados em diferentes culturas em todo o mundo. Ele é um elemento-chave dos algoritmos RSA, um método de criptografia de chave pública usado no comércio eletrônico. Ele é usado para resolver as equações de diofantina, tal como na descoberta de números que seja safistatório em múltiplas congruências (teorema chinês do resto) ou inverso multiplicativo de um número finito. Ele pode também ser usado para construir frações contínuas, em um método para o teorema de Sturm para descobrir raízes reais em um polinômio, e em vários algoritmos modernos em fatoração de inteiros. Finalmente, é uma ferramenta básica para obter na teoria dos números modernas, tal como teorema de Fermat-Lagrange e no teorema fundamental da aritmética.